package cn.lishiyuan.algorithm.graph;

import cn.lishiyuan.algorithm.heap.Heap;
import cn.lishiyuan.algorithm.queue.LeeQueue;
import cn.lishiyuan.algorithm.queue.LinkedQueue;

import java.util.*;

/**
 * 邻接表
 */
public class AdjacencyList<V> implements Graph<V>,TopoSort<V> {
    // 顶点
    private Set<V> vertices;
    // 边
    private Map<V,Map<V,Integer>> edges;

    private GraphType type;


    public AdjacencyList(Set<V> nodes,GraphType type) {
        if (nodes == null || nodes.isEmpty()){
            throw new IllegalArgumentException("nodes is null or empty");
        }

        if (type == null){
            throw new IllegalArgumentException("type is null");
        }

        this.type = type;
        this.vertices = new HashSet<>(nodes);
        this.edges = new HashMap<>();
    }


    @Override
    public void addEdge(V from, V to, int weight) {
        boolean fromExists = this.vertices.contains(from);
        boolean toExists = this.vertices.contains(to);
        if (!fromExists || !toExists){
            throw new IllegalArgumentException("顶点不存在");
        }

        // 有向图
        Map<V,Integer> toEdges = this.edges.getOrDefault(from,new HashMap<>());
        toEdges.put(to,weight);
        this.edges.put(from,toEdges);

        if(type == GraphType.GRAPH){
            // 无向图
            Map<V, Integer> fromEdges = this.edges.getOrDefault(to, new HashMap<>());
            fromEdges.put(from,weight);
            this.edges.put(to,fromEdges);
        }

    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, 1);
    }

    @Override
    public void removeEdge(V from, V to) {
        boolean fromExists = this.vertices.contains(from);
        boolean toExists = this.vertices.contains(to);
        if (!fromExists || !toExists){
            throw new IllegalArgumentException("顶点不存在");
        }

        // 有向图
        Map<V,Integer> toEdges = this.edges.getOrDefault(from,new HashMap<>());
        toEdges.remove(to);
        this.edges.put(from,toEdges);

        if(type == GraphType.GRAPH){
            // 无向图
            Map<V, Integer> fromEdges = this.edges.getOrDefault(to, new HashMap<>());
            fromEdges.remove(from);
            this.edges.put(to,fromEdges);
        }
    }

    @Override
    public int getWeight(V from, V to) {
        boolean fromExists = this.vertices.contains(from);
        boolean toExists = this.vertices.contains(to);
        if (!fromExists || !toExists){
            throw new IllegalArgumentException("顶点不存在");
        }
        Map<V,Integer> toEdges = this.edges.getOrDefault(from,new HashMap<>());
        return toEdges.getOrDefault(to, 0);
    }

    @Override
    public boolean existsEdge(V from, V to) {
        return getWeight(from,to) > 0;
    }

    @Override
    public int getInDegree(V vertex) {
        if (!this.vertices.contains(vertex)){
            return 0;
        }

        int degree = 0;
        if (type == GraphType.GRAPH){
            Map<V, Integer> toEdges = edges.getOrDefault(vertex, new HashMap<>());
            degree = toEdges.size();
        }else {
            for (V v : vertices) {
                if (v.equals(vertex)){
                    continue;
                }
                Map<V,Integer> edgeSet = edges.getOrDefault(v, new HashMap<>());
                if (edgeSet.containsKey(vertex)){
                    degree ++;
                }
            }
        }

        return degree;
    }

    @Override
    public int getOutDegree(V vertex) {
        if (!this.vertices.contains(vertex)){
            return 0;
        }
        Map<V,Integer> edgeSet = edges.getOrDefault(vertex, new HashMap<>());
        return edgeSet.size();
    }

    @Override
    public int getVertexCount() {
        return vertices.size();
    }

    @Override
    public int getEdgeCount() {
        int edgeCount = 0;
        for (Map<V,Integer> edgeSet : edges.values()){
            edgeCount += edgeSet.size();
        }
        // 无向图边除以2
        if (type == GraphType.GRAPH){
            edgeCount  = edgeCount / 2;
        }
        return edgeCount;
    }

    @Override
    public List<V> path(V from, V to) {
        // Dijkstra 最短路径算法实现
        if (!this.vertices.contains(from) || !this.vertices.contains(to)){
            return Collections.emptyList();
        }

        // 当前节点到起始节点的最短距离
        Map<V,Integer> distance = new HashMap<>();
        // 当前节点的上个节点
        Map<V,V> before = new HashMap<>();
        // 当前节点是否在队列中
        List<V> inHeap = new ArrayList<>();

        // 小顶堆
        Heap<Node<V>> heap = new Heap<>(Heap.HeapType.MIN,vertices.size());
        Node<V> fromNode = new Node<>();
        fromNode.distance = 0;
        fromNode.v = from;
        inHeap.add(from);
        heap.add(fromNode);

        while (!heap.isEmpty()) {
            Node<V> top = heap.removeTop();
            // 已经取出
            inHeap.remove(top.v);

            // 不存在相连的边
            Map<V, Integer> edge = edges.get(top.v);
            if (edge == null || edge.isEmpty()){
                continue;
            }

            for (Map.Entry<V, Integer> entry : edge.entrySet()) {
                // 上次的最短距离
                Integer dist = distance.get(entry.getKey());
                // 当前距离
                int nowDist = entry.getValue() + top.distance;
                Node<V> node = new Node<>();
                node.v = entry.getKey();
                // 是否需要堆化
                boolean needHeap = false;

                if (dist == null){
                    // 第一次
                    node.distance = nowDist;
                    distance.put(entry.getKey(),nowDist);
                    before.put(entry.getKey(), top.v);
                    needHeap = true;
                }else if (nowDist < dist){
                    // 已经放入过堆
                    node.distance = nowDist;
                    distance.put(entry.getKey(),nowDist);
                    before.put(entry.getKey(), top.v);
                    needHeap = true;
                }else{
                    // 不需要处理
                    node.distance = dist;
                }

                if (needHeap){
                    if (inHeap.contains(entry.getKey())) {
                        // 更新heap
                        heap.update(node);
                    }else {
                        inHeap.add(entry.getKey());
                        heap.add(node);
                    }
                }
            }
        }

        List<V> path = new ArrayList<>();
        // 逆向推断出路径
        if(before.containsKey(to)){
            path.add(to);

            V now = before.get(to);
            while (now!=null){
                path.add(now);
                now = before.get(now);
            }
        }

        return path;
    }

    @Override
    public int distance(V from, V to) {
        // Dijkstra 最短路径算法实现
        if (!this.vertices.contains(from) || !this.vertices.contains(to)){
            return -1;
        }

        // 当前节点到起始节点的最短距离
        Map<V,Integer> distance = new HashMap<>();
        // 当前节点是否在队列中
        List<V> inHeap = new ArrayList<>();


        Heap<Node<V>> heap = new Heap<>(Heap.HeapType.MIN,vertices.size());
        Node<V> fromNode = new Node<>();
        fromNode.distance = 0;
        fromNode.v = from;
        inHeap.add(from);
        heap.add(fromNode);

        while (!heap.isEmpty()) {
            Node<V> top = heap.removeTop();
            inHeap.remove(top.v);

            Map<V, Integer> edge = edges.get(top.v);
            if (edge == null || edge.isEmpty()){
                continue;
            }
            for (Map.Entry<V, Integer> entry : edge.entrySet()) {
                Integer dist = distance.get(entry.getKey());
                int nowDist = entry.getValue() + top.distance;
                Node<V> node = new Node<>();
                node.v = entry.getKey();
                boolean needHeap = false;
                if (dist == null){
                    node.distance = nowDist;
                    distance.put(entry.getKey(),nowDist);
                    needHeap = true;
                }else if (nowDist < dist){
                    node.distance = nowDist;
                    distance.put(entry.getKey(),nowDist);
                    needHeap = true;
                }else{
                    node.distance = dist;
                }

                if (needHeap){
                    if (inHeap.contains(entry.getKey())) {
                        // 更新heap
                        heap.update(node);
                    }else {
                        inHeap.add(entry.getKey());
                        heap.add(node);
                    }
                }
            }
        }

        return distance.getOrDefault(to,-1);
    }

    private static class Node<V> implements Comparable<Node<V>>{
        V v;
        int distance;

        @Override
        public int compareTo(Node o) {
            return distance - o.distance;
        }

        @Override
        public boolean equals(Object obj) {
            boolean eq= super.equals(obj);
            if(!eq && obj instanceof Node){
                eq = v.equals( ((Node<?>) obj).v);
            }
            return eq;
        }
    }




    @Override
    public List<V> search(V from, V to) {
        return bfs(from,to);
    }

    // 广度优先搜索
    private List<V> bfs(V from, V to){
        if(Objects.equals(from,to)){
            return Collections.singletonList(to);
        }

        // 队列存储待处理的顶点
        LeeQueue<V> queue = new LinkedQueue<>();
        queue.enqueue(from);
        // 已经访问过的顶点
        Set<V> visited = new HashSet<>();
        visited.add(from);

        // 节点的前向顶点
        Map<V,V> prev = new HashMap<>();

        // 如果队列不为空，则遍历查找
        while (!queue.isEmpty()){
            V node = queue.dequeue();
            // 与边相连的节点
            Map<V, Integer> edgeInfo = edges.getOrDefault(node,new HashMap<>());
            for (V v : edgeInfo.keySet()){
                if (!visited.contains(v)){
                    // 存储前向节点
                    prev.put(v,node);
                    // 已找到，返回数据
                    if(v.equals(to)){
                        // 已找到
                        List<V> result = new ArrayList<>();
                        result.add(v);

                        V prevV = prev.get(v);
                        while (prevV != null){
                            result.add(prevV);
                            prevV = prev.get(prevV);
                        }
                        Collections.reverse(result);
                        return result;
                    }
                    // 将节点加入对列尾部
                    queue.enqueue(v);
                    // 标记为已处理
                    visited.add(v);
                }
            }
        }

        //

        return Collections.emptyList();
    }

    @Override
    public List<V> sort() {
        // Kahn 算法
        // 构建逆邻接表
        Map<V,Map<V,Integer>> inverseEdges = new HashMap<>();
        for (Map.Entry<V, Map<V, Integer>> entry : edges.entrySet()) {
            V key = entry.getKey();
            Map<V,Integer> edgeInfo = entry.getValue();
            for (Map.Entry<V, Integer> value : edgeInfo.entrySet()) {
                Map<V, Integer> integerMap = inverseEdges.getOrDefault(value.getKey(), new HashMap<>());
                integerMap.put(key,value.getValue());
                inverseEdges.put(value.getKey(),integerMap);
            }
        }

        List<V> list = new ArrayList<>();

        LeeQueue<V> queue = new LinkedQueue<>();
        // 将一开始就没有入度元素加入到队列
        for (V vertex : vertices) {
            Map<V, Integer> vIntegerMap = inverseEdges.get(vertex);
            // 没有入度
            if(vIntegerMap == null || vIntegerMap.isEmpty()){
                queue.enqueue(vertex);
            }
        }

        while (!queue.isEmpty()){
            V vertex = queue.dequeue();
            list.add(vertex);

            inverseEdges.remove(vertex);
            // 获取出度
            Map<V, Integer> map = edges.get(vertex);
            if (map != null){
                for (V v : map.keySet()) {
                    // 删除对应顶点的入度
                    Map<V, Integer> edgesOrDefault = inverseEdges.getOrDefault(v, new HashMap<>());
                    edgesOrDefault.remove(vertex);
                    // 没有入度了
                    if (edgesOrDefault.isEmpty()){
                        queue.enqueue(v);
                    }
                }
            }

        }

        return list;
    }

    /**
     * 转换成邻接矩阵
     * @return
     */
    public AdjacencyMatrix<V> transfer(){
        V[] data = vertices.toArray((V[]) new Object[0]);
        AdjacencyMatrix<V> adjacencyMatrix = new AdjacencyMatrix<V>(data,type);

        for (V v : data) {
            Map<V,Integer> edgeSet = edges.getOrDefault(v, new HashMap<>());

            for (Map.Entry<V, Integer> entry : edgeSet.entrySet()) {
                adjacencyMatrix.addEdge(v,entry.getKey(),entry.getValue());
            }
        }

        return adjacencyMatrix;
    }

}
